package com.hy;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:找出所有子集的异或总和再求和
 *
 * 一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果；如果数组为 空 ，则异或总和为 0 。
 * 例如，数组 [2,5,6] 的 异或总和 为 2 XOR 5 XOR 6 = 1 。
 * 给你一个数组 nums ，请你求出 nums 中每个 子集 的 异或总和 ，计算并返回这些值相加之 和 。
 * 注意：在本题中，元素 相同 的不同子集应 多次 计数。
 * 数组 a 是数组 b 的一个 子集 的前提条件是：从 b 删除几个（也可能不删除）元素能够得到 a 。
 *
 * author: Mr.Du
 * Date: 2023/10/18
 * Time: 10:26
 */
public class SubsetXORSum {
    int num = 0;
    int sum = 0;
    public int subsetXORSum(int[] nums) {
        dfs(nums, 0);
        return sum;
    }

    /**
     * 解法和子集这道解法几乎一致，
     * @param nums
     * @param start
     */
    public void dfs(int[] nums, int start){
        sum += num;
        if(start == nums.length) return;
        for(int i = start;i < nums.length;i++){
            // 记录当前num
            int tmp = num;
            num ^= nums[i];
            dfs(nums, i + 1);
            // 回退
            num = tmp;
        }
    }
}
